package com.dynamicprogram;

import java.util.Map;

public class Solution740 {
    public int deleteAndEarn(int[] nums) {
        int[] dp = new int[10001];
        int[] count = new int[10001];
        for (int x : nums) {
            count[x]++;
        }
        dp[1] = count[1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + count[i] * i);
        }
        return dp[10000];
    }
}
